/**
 * 给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
 *
 *https://leetcode.cn/problems/remove-duplicate-letters/
 */
class RemoveDuplicateLetters {
    public String removeDuplicateLetters(String s) {
        int len=s.length();
        int[] count=new int[256];// 维护一个计数器记录字符串中字符的数量 因为输入为 ASCII 字符，大小 256 够用了
        boolean[] inStack=new boolean[256];
        Deque<Character> stack=new LinkedList<>();
        for(int i=0;i<len;i++) {
            // 每遍历过一个字符，都将对应的计数减一
            count[s.charAt(i)]++;
        }
        int i=0;
        while(i<len) {
            // 若之后不存在栈顶元素了，则停止 pop
            char c=s.charAt(i);
            count[c]--;
             i++;
            if(inStack[c]) {
               
                continue;
            }
            while(!stack.isEmpty()&&stack.peekLast()>c) {
                if(count[stack.peekLast()]==0) {
                    break;
                }
                 // 若之后还有，则可以 pop
               inStack[stack.pollLast()]=false;
            }
            stack.addLast(c);
            inStack[c]=true;
          
        }
        StringBuilder ans=new StringBuilder();
        while(!stack.isEmpty()) {
            ans.append(stack.pollFirst());
        }
        return ans.toString();
    }
}